home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 11 - 1995 / 11.10 Oct 95 / Diff-Warrior.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-08-14  |  24.8 KB  |  862 lines  |  [TEXT/Rich]
  1. /*
  2.   11 August 1995.
  3.  
  4.   Submission to MacTech Programmer's challenge August 1995.
  5.  
  6.   Copyright 1995, Ernst Munter, Kanata, ON, Canada.
  7.  
  8.         The problem and the solution:
  9.         ---------------------------------
  10.  
  11.   Given two texts, compute a series of insert/delete/move
  12.   instructions that will describe the conversion of one
  13.   text into the other.
  14.  
  15.   I parse the old text, and create a sequential word list.
  16.   The words are further linked into lists, accessed through
  17.   a hash table.
  18.  
  19.   Then, I parse the second text, and for each word in the
  20.   second text, I try to find a matching word in the first
  21.   text.  The hashed table of lists helps me find the first
  22.   matching word quickly.  I remove it from the list, and
  23.   mark it for a potential move operation.
  24.  
  25.   Each matching word found in the first text may either
  26.   remain in place, or must be moved.
  27.  
  28.   There exists an algorithm to determine the best set
  29.   of words (most characters) to leave undisturbed, and so
  30.   minimize the amount to be moved.  However, I did not have
  31.   the patience to work this out fully.
  32.  
  33.   So, as a compromise solution, I just go sequentially
  34.   through the texts together, and make an educated guess
  35.   for each block of contiguous matching words, to decide
  36.   whether to leave or move them.
  37.  
  38.   Any words encountered in the new text that are not found
  39.   in the old text are immediately marked for "insert".
  40.   After the whole text is scanned, any words or blocks
  41.   left behind in the hash lists, are destined for deletion.
  42.   Before the parsing, a character by character comparison
  43.   of the two texts is done from each end, to cut off all
  44.   text which is equal and does not need any further
  45.   analysis.  This may result in the discovery that both
  46.   texts are identical.  All other special cases, such as
  47.   only a single change at one end or in the middle of one
  48.   of the texts, will be automatically handled.
  49.  
  50.   Before returning the DiffRecs to the caller, I analyze
  51.   pairs of inserts and deletes to eliminate redundancies.
  52.  
  53.   The program will allocate a fair amount of memory to
  54.   build the word lists in.  This can be minimized by
  55.   doing a word count first.  But I prefer to just provide
  56.   a conservative factor (4 chars per word, white space
  57.   included) which should be enough for normal texts.
  58.   Please use the "countWords" directive if memory must
  59.   be conserved.
  60.  
  61.   I have allocated a fixed static hash table of 997
  62.   entries.  With 65000 bytes, and say, 6.5 bytes per
  63.   word really, each list would contain 10 entries on
  64.   the average.  hashMod can easily be increased to
  65.   some larger prime number to speed up word lookup for
  66.   large files.
  67.  
  68.   I have also provided a lookup table for determining
  69.   what characters are considered parts of words, and
  70.   which are white space.  Include foreign letters and
  71.   digits if that is desirable.  If the texts are
  72.   computer programs, underscore and other symbols
  73.   might be included in "alpha", depending on the language.
  74.  
  75. */
  76.  
  77. #include <stdio.h>
  78. #include <stdlib.h>
  79.  
  80. #define ulong unsigned long
  81. #define ushort unsigned short
  82.  
  83. typedef enum {
  84.   deletedText=0, insertedText, movedText } DiffType;
  85.  
  86. typedef struct {
  87.   DiffType      type;
  88.   ulong         rangeStart;
  89.   ulong         rangeEnd;
  90.   ulong         position;
  91. } DiffRec;
  92.  
  93. short FindWordDifferences (
  94.   char          *oldText,
  95.   char          *newText,
  96.   ulong         numOldChars,
  97.   ulong         numNewChars,
  98.   DiffRec       diffs[],
  99.   ulong         maxDiffRecs);
  100.  
  101. #define countWords 0
  102.  
  103. #if countWords
  104. /*use the actual word count to reserve Snippet space*/
  105. #else
  106. /*use a very conservative estimate to reserve enough*/
  107. #define averageWordSize 4
  108. #endif
  109.  
  110. #define hashMod 997 //any reasonable prime number
  111.  
  112. #define inDelete  0 //state values during text scan
  113. #define inMove    1
  114. #define inInsert  2
  115. #define inLimbo   3
  116.  
  117. #define nullRec   3 //used to mark redundant DiffRecs
  118.  
  119.  
  120. /*A word is defined as a contiguous sequence of letters
  121.   from the set defined in the lookup table.
  122.  
  123.   The table defaults to 'A'-'Z','a'-'z', but foreign
  124.   characters or digits are easily included if desired.
  125. */
  126.  
  127. #define includeForeign  0
  128. #define includeDigits   0
  129.  
  130. static char lookup[256] = {
  131.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //control
  132.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //control
  133.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //punctuation
  134. #if includeDigits
  135.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //digits plus
  136. #else
  137.   1,1,1,1,1,1,1,1, 1,1,0,0,0,0,0,0,     //digits plus
  138. #endif
  139.   0,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,     //caps A-O
  140.   1,1,1,1,1,1,1,1, 1,1,1,0,0,0,0,0,     //caps P-Z
  141.   0,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,     //small a-o
  142.   1,1,1,1,1,1,1,1, 1,1,1,0,0,0,0,0,     //small p-z
  143. #if includeForeign
  144.   1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,     //foreign caps
  145.   1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,     //foreign small
  146.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //symbols
  147.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //symbols
  148.   0,0,0,0,0,0,0,0, 0,0,0,1,1,1,1,1,     //symbols plus
  149.   0,0,0,0,0,0,0,0, 1,1,0,0,0,0,0,0,     //symbols plus
  150. #else
  151.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //foreign caps
  152.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //foreign small
  153.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //symbols
  154.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //symbols
  155.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //symbols plus
  156.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //symbols plus
  157. #endif
  158.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,     //graphic chars
  159.   0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0      //graphic chars
  160. };
  161.  
  162. #define isAlpha(x) lookup[x]
  163.  
  164. /*A snippet may describe a word or a block of words
  165.   in the old text and includes the white space.
  166.   The reference to the new text is used to track
  167.   the equivalent position in the new text.
  168. */
  169. typedef struct Snippet {
  170.   DiffType      type;
  171.   char*         oldTextRef;
  172.   char*         newTextRef;
  173.   ulong         length;
  174.   void*         next;
  175. } Snippet;
  176.  
  177. /*The hashTable is an array of lists where each list
  178.   contains the snippets (words or blocks) from the
  179.   old text which hash to the same value, in the order
  180.   in which they occured.
  181. */
  182. typedef struct List {
  183.   Snippet*      first;
  184.   Snippet*      last;
  185. } List;
  186.  
  187. static List hashTable[hashMod];
  188. static Snippet* snippetStore;   //allocated as needed
  189. static ushort   numSnippets;
  190. static ushort   nextFreeSnippet;
  191.  
  192.  
  193. /*The hash function is used to distribute different
  194.   snippets into different lists as evenly as possible.
  195. */
  196. ushort Hash(char* text,ulong numChars)
  197. {
  198.   register ulong accumulator=numChars;
  199.   if (numChars>6) numChars=6;
  200.   switch (numChars) {
  201. case 6:accumulator=(accumulator<<5)+*text++;
  202. case 5:accumulator=(accumulator<<5)+*text++;
  203. case 4:accumulator=(accumulator<<5)+*text++;
  204. case 3:accumulator=(accumulator<<5)+*text++;
  205. case 2:accumulator=(accumulator<<5)+*text++;
  206. case 1:accumulator=(accumulator<<5)+*text++;
  207. case 0:;
  208.   }
  209.   return accumulator % hashMod;
  210. }
  211.  
  212. /*Clears all snippets to 0*/
  213. void ClearSnippetStore()
  214. {
  215.   Snippet* s=snippetStore;
  216.   ushort n=numSnippets-1;
  217.   s->type=deletedText;
  218.   s->oldTextRef=0;
  219.   s->newTextRef=0;
  220.   s->length=0;
  221.   s->next=0;
  222.   s++;
  223.   while (n--) *s++=*snippetStore;
  224. }
  225.  
  226. /*Preallocates an array of snippets to handle oldText.
  227.   All snippets are initially marked deletedText.
  228. */
  229. void GetSnippetStore(ulong snippetsAllocated)
  230. {
  231.   ulong memoryRequired;
  232.   if (snippetsAllocated>65535) snippetsAllocated=65535;
  233.   numSnippets=(ushort)snippetsAllocated;
  234.   memoryRequired=numSnippets*sizeof(Snippet);
  235.   snippetStore=(Snippet*)malloc(memoryRequired);
  236.   ClearSnippetStore();
  237.   nextFreeSnippet=0;
  238. }
  239.  
  240. /*Assign the next snippet from the preallocated array.*/
  241. Snippet* NewSnippet(char* text)
  242. {
  243.   register Snippet* s;
  244.   s=&(snippetStore[nextFreeSnippet++]);
  245.   s->oldTextRef=text;
  246.   return s;
  247. }
  248.  
  249. /*Consecutive Snippets are merged into larger blocks*/
  250. int ExtendSnippet(Snippet* oldS,Snippet* s)
  251. {
  252.   if (oldS->oldTextRef+oldS->length==s->oldTextRef) {
  253.     oldS->length+=s->length;
  254.     s->length=0;
  255.     return 1;
  256.   }
  257.   return 0;
  258. }
  259.  
  260. /*Snippets are attached at end of a list (hashTable[])*/
  261. void Record(Snippet* s)
  262. { register List* list=
  263.         &(hashTable[Hash(s->oldTextRef,s->length)]);
  264.   register Snippet* lastS=list->last;
  265.   if (lastS) lastS->next=s;
  266.   else list->first=s;
  267.   list->last=s;
  268. }
  269.  
  270. /*Matches two substrings of length numChars*/
  271. int Match(char* text0,char* text1,ulong numChars)
  272. {
  273.   while (numChars--) {
  274.     if (*text0!=*text1) return 0;
  275.     text0++;
  276.     text1++;
  277.   }
  278.   return 1;
  279. }
  280.  
  281. /*Snippets of the oldText are matched against a word from
  282.   newText.  The first matching word is removed from the
  283.   hash list.
  284. */
  285. Snippet* FindAndRemoveSnippet(char* text,ulong numChars)
  286. {
  287.   List* list=&(hashTable[Hash(text,numChars)]);
  288.   Snippet* s=list->first;
  289.   Snippet* father=0;
  290.   while (s) {
  291.     if ((s->length==numChars)
  292.         && Match(s->oldTextRef,text,numChars)) break;
  293.     father=s;
  294.     s=(Snippet*)(s->next);
  295.   }
  296.   if (father) {
  297.     father->next=s->next;
  298.     if (list->last==s) list->last=father;
  299.   } else list->first=list->last=0;
  300.   return s;
  301. }
  302.  
  303. /*The following macros set up the 3 different types of
  304.   DiffRecs.
  305. */
  306. #define StartMoveRecord                                 \
  307. { diffPtr->type=movedText;                              \
  308.   diffPtr->rangeStart=block->oldTextRef-oldText;        \
  309.   diffPtr->rangeEnd=diffPtr->rangeStart+block->length-1;\
  310.   diffPtr->position=startOfText->oldTextRef+            \
  311.     startOfText->length-oldText;                        \
  312. }
  313.  
  314. #define StartInsertRecord                               \
  315. { diffPtr->type=insertedText;                           \
  316.   diffPtr->rangeStart=text-newText;                     \
  317.   diffPtr->rangeEnd=diffPtr->rangeStart+wordLength-1;   \
  318.   diffPtr->position=startOfText->oldTextRef+            \
  319.     startOfText->length-oldText;                        \
  320. }
  321.  
  322. #define StartDeleteRecord                               \
  323. { diffPtr->type=deletedText;                            \
  324.   diffPtr->rangeStart=block->oldTextRef-oldText;        \
  325.   diffPtr->rangeEnd=diffPtr->rangeStart+block->length-1;\
  326.   diffPtr->position=block->newTextRef-newText;          \
  327. }
  328.  
  329. /*The following macro marks all words from startOfText
  330.   to "toHere" as potential candidates for delete.
  331.   Any of the words will be overwritten and become movedText
  332.   if they end up being matched in newText later.
  333. */
  334. #define MarkDeletedWords(toHere)                        \
  335. { canDel=startOfText;                                   \
  336.   while (++canDel<toHere)                               \
  337.     if (canDel->type==deletedText)                      \
  338.       canDel->newTextRef=markNew;                       \
  339. }
  340.  
  341. /*
  342.   A matching word may be found in the old text at a point
  343.   far beyond the current insertion point.  It would be
  344.   a shame to declare this word the new insertion point,
  345.   and then have to move all intervening words (yet to
  346.   be matched).  It is better to move the smaller block
  347.   or word up.  This macro is a heuristic attempt to
  348.   make a sensible guess as to which block is larger,
  349.   the matching word (100%) or the intervening text
  350.   (adjusted according to the ratio of remaining chars
  351.   still required for matching, at 50%).
  352. */
  353. #define BestGuess                                       \
  354.   (skippedChars*(remainingNew>>1)>                      \
  355.     block->length*remainingOld)
  356.  
  357. /*Words are extracted by first scanning through any
  358.   preceding white space, then by scanning through the
  359.   alpha characters, until another white space occurs.
  360.  
  361.   It is assumed that \x0 does not occur as part of either
  362.   text.  The last character in the text is then temporarily
  363.   set to 0 so we easily find the end of text.
  364. */
  365. #define NextWord                                        \
  366. { while ((*t)&&(0==isAlpha(*t))) t++;                   \
  367.   while (0!=isAlpha(*t)) t++;                           \
  368. }
  369.  
  370. #define EmitRecord                                      \
  371. { diffPtr++;                                            \
  372.   if (diffPtr-diffs>=maxDiffRecs) return maxDiffRecs;   \
  373. }
  374.  
  375. #define ClearHashTable                                  \
  376. { ushort n=hashMod;                                     \
  377.   List* H=hashTable;                                    \
  378.   while (n--) {                                         \
  379.     H->first=0;                                         \
  380.     H->last=0;                                          \
  381.     H++;                                                \
  382.   }                                                     \
  383. }
  384.  
  385. /*The function ParseOldText scans the oldText and creates
  386.   an array of snippets, where each snippet corresponds to
  387.   one word.  In addition, each snippet is linked into a
  388.   list, where each list is headed by a List pointer in
  389.   hashTable.
  390.   The last character of the text is temporarily set to 0
  391.   as an end-of-text marker.
  392. */
  393. void ParseOldText(
  394. char* oldText,
  395. ulong numSameHead,
  396. ulong numChars)
  397. {
  398.   Snippet*      s;
  399.   char*         text=oldText+numSameHead;
  400.   char*         t;
  401.   char          lastChar=text[numChars-1]; //save it
  402.   text[numChars-1]=0;
  403.   ClearHashTable;
  404.   t=text;
  405.   NewSnippet(text);
  406.   //A null snippet anchors the start of the text.
  407.   do {
  408.     NextWord;
  409.     s=NewSnippet(text);
  410.     s->length=t-text;
  411.     if (0==*t) break;
  412.     Record(s);
  413.     text=t;
  414.   } while (1);
  415.   *t=lastChar;           //restore the last char
  416.   s->length++;
  417.   Record(s);
  418. }
  419.  
  420. /* The ParseNewText function scans the newText and tries
  421.    to match it with the oldText.
  422.  
  423.    It proceeds by isolating words, and matching them
  424.    against previously created Snippets (see ParseOldText).
  425.  
  426.    It is a state machine which tries to agglomerate
  427.    contiguous blocks of words while it is in either
  428.    the insert or move state.  When it switches states
  429.    it creates a DiffRec for the preceding block.
  430.  
  431.    It moves the "startOfText" in the oldText along as it
  432.    scans the newText and encounters matching blocks.
  433.  
  434.    If the accumulated matching (movedText) block lies
  435.    before the current startOfText, or if it is small
  436.    and lies far forward, it is made into a movedText record.
  437.    But otherwise, it stays un-moved, and becomes the
  438.    new startOfText.
  439.  
  440.    Blocks of contiguous words assembled during the insert
  441.    state (i.e. no matching words in oldText) are also
  442.    accumulated and result in insertedText records.
  443.  
  444.    DeletedText records are created later, after all text has
  445.    been scanned, by collecting the leftovers in oldText,
  446.    (see CollectDeletes below).
  447. */
  448. short ParseNewText( //returns number of inserted DiffRecs
  449. char* oldText,
  450. char* newText,
  451. DiffRec* diffs,
  452. ulong numSameHead,
  453. ulong numOldChars,
  454. ulong numNewChars,
  455. ulong maxDiffRecs)
  456. {
  457.   Snippet*      s;
  458.   Snippet*      canDel;
  459.   Snippet*      block;
  460.   Snippet*      startOfText=snippetStore;//null snippet
  461.   Snippet*      endOfText=
  462.                 NewSnippet(oldText+numSameHead+numOldChars);
  463.   char*         text=newText+numSameHead;
  464.   char*         markNew=text;
  465.   char*         t;
  466.   DiffRec*      diffPtr=diffs;
  467.   ulong         wordLength;
  468.   ulong         remainingNew=numNewChars;
  469.   ulong         remainingOld=numOldChars;
  470.   long          skippedChars;   // signed !
  471.   int           state=inLimbo;
  472.   char          lastChar;
  473.   char          done=0;
  474.  
  475.   if (0==numNewChars) goto cleanup;
  476.   lastChar=text[numNewChars-1];
  477.   text[numNewChars-1]=0;
  478.   do {
  479.     t=text;
  480.     NextWord;
  481.     wordLength=t-text;
  482.     if (0==*t) {
  483.       *t=lastChar;      //restore last char
  484.       wordLength++;
  485.       done=1;
  486.     }
  487.     if (0!=(s=FindAndRemoveSnippet(text,wordLength))) {
  488.       s->type=movedText;
  489.       remainingOld-=s->length;
  490.       remainingNew-=s->length;
  491.       switch (state) {
  492.       case inMove:
  493.         if (0==ExtendSnippet(block,s)) {
  494.           skippedChars=block->oldTextRef-
  495.             startOfText->oldTextRef-startOfText->length;
  496.           if ((skippedChars<0) || BestGuess) {
  497.             StartMoveRecord;
  498.             EmitRecord;
  499.           } else {
  500.             MarkDeletedWords(block);
  501.             startOfText=block;
  502.           }
  503.           block=s;
  504.         }
  505.         break;
  506.       case inInsert:
  507.         EmitRecord;
  508.       case inLimbo:
  509.         block=s;
  510.         markNew=text;
  511.         state=inMove;
  512.       }
  513.     } else {
  514.       remainingNew-=wordLength;
  515.       switch (state) {
  516.       case inInsert:
  517.         diffPtr->rangeEnd+=wordLength;
  518.         break;
  519.       case inMove:
  520.         skippedChars=block->oldTextRef-
  521.                 startOfText->oldTextRef-startOfText->length;
  522.         if ((skippedChars<0) || BestGuess) {
  523.           StartMoveRecord;
  524.           EmitRecord;
  525.         } else {
  526.           MarkDeletedWords(block);
  527.           startOfText=block;
  528.         }
  529.       case inLimbo:
  530.         StartInsertRecord;
  531.         state=inInsert;
  532.       }
  533.     }
  534.     text=t;
  535.   } while (0==done);
  536.  
  537. cleanup:
  538.   switch (state) {
  539.   case inMove:
  540.     skippedChars=block->oldTextRef-
  541.       startOfText->oldTextRef-startOfText->length;
  542.     if (skippedChars<0) {
  543.       StartMoveRecord;
  544.     } else {
  545.       MarkDeletedWords(endOfText);
  546.       break;
  547.     }
  548.   case inInsert:
  549.     EmitRecord;
  550.   case inLimbo:
  551.     MarkDeletedWords(endOfText);
  552.   }
  553.  
  554.   return diffPtr-diffs;
  555. }
  556.  
  557. /*The CollectDeletes function scans through the entire
  558.   snippet array, and detects all snippets still marked
  559.   as deletedText.  Contiguous blocks of these are
  560.   assembled to generate deletedText DiffRecs.
  561. */
  562. short CollectDeletes(
  563. DiffRec* diffs,
  564. char* oldText,
  565. char* newText,
  566. ulong maxDiffRecs)
  567. {
  568.   DiffRec*      diffPtr=diffs;
  569.   Snippet*      s=snippetStore;
  570.   Snippet*      block;
  571.   ushort        n=nextFreeSnippet;
  572.   int           state=inLimbo;
  573.   while (n--) {
  574.     if (s->length) {
  575.       if (s->type==deletedText) {
  576.         if (state==inLimbo) {
  577.           block=s;
  578.           state=inDelete;
  579.         } else block->length+=s->length;
  580.       } else if (state==inDelete) {
  581.         StartDeleteRecord;
  582.         EmitRecord;
  583.         state=inLimbo;
  584.       }
  585.     }
  586.     s++;
  587.   }
  588. //cleanup:
  589.   if (state==inDelete) {
  590.     StartDeleteRecord;
  591.     diffPtr++;
  592.   }
  593.  
  594.   return diffPtr-diffs;
  595. }
  596.  
  597. #if countWords
  598. /*This function could be used to tailor make the number of
  599.   snippets in snippetStore to the exact number required
  600. */
  601. short WordCount(char* text,ulong numChars)
  602. {
  603.   register      char*   t=text;
  604.   short                 WC=1;
  605.   char                  lastChar;
  606.   if (numChars<=1) return numChars;
  607.   lastChar=t[numChars-1];
  608.   t[numChars-1]=0;
  609.   do {
  610.     NextWord;
  611.     WC++;
  612.   } while (*t);
  613.   *t=lastChar;
  614.   return WC;
  615. }
  616. #endif
  617.  
  618. /*Null records can result from cancelling common parts
  619.   of insert/delete pairs, for example insert " [The"
  620.   and delete " The" would become just insert "[".
  621.   The delete record would have a length of 0, i.e.
  622.   a rangeEnd below rangeStart.  If this occurred
  623.   at the start of text, the value 0xFFFFFFFF would
  624.   occur for rangeEnd, surely not a good thing.
  625.   It is surely best to eliminate those null records.
  626. */
  627. void ExtractNullRecs(DiffRec* diffs,short numDiffRecs)
  628. {
  629.   DiffRec*      d=diffs+numDiffRecs;
  630.   short         i=numDiffRecs;
  631.   short         numMove;
  632.   while (i--) {
  633.     d--;
  634.     if (d->type==nullRec) {
  635.       DiffRec* dx=d+1;
  636.       numDiffRecs--;
  637.       numMove=numDiffRecs-i;
  638.       while (numMove--) *d++=*dx++;
  639.       numMove=i;
  640.     }
  641.   }
  642. }
  643.  
  644. /*Since all snippets (and hence DiffRecs) refer to
  645.   words which usually include leading white space,
  646.   the might differ as such, but have common white
  647.   space with different words, or vice versa.
  648.   The ReduceInsDelPairs attempts to match pairs
  649.   at the same text location, and remove their
  650.   common parts.
  651.  
  652.   The loop relies on the existing order of records,
  653.   as created by ParseNewText, followed by CollectCeletes.
  654.   This means delete records are at the end, and all
  655.   are in the order of the text.  Ins and Del records
  656.   are compared if they apply to the same insertion/
  657.   deletion point, and   share common words or white space
  658.   at either end of the block.  The aggregation of blocks
  659.   hurts sometimes, in that redundancies in the middle
  660.   will not be found here.
  661. */
  662. short ReduceInsDelPairs(
  663. DiffRec* diffs,
  664. short numDiffRecs,
  665. char* oldText,
  666. char* newText)
  667. {
  668.   DiffRec*      dRec=diffs+numDiffRecs-1;
  669.   DiffRec*      iRec=dRec;
  670.   short          eliminated=0;
  671.   while (iRec>diffs) {
  672.     iRec--;
  673.     if (insertedText==iRec->type) break;
  674.   }
  675.   while (dRec>diffs) {
  676. top_of_loop:
  677.     if (deletedText!=dRec->type) break;
  678.     if (dRec->rangeStart>iRec->position) {
  679.       dRec--;
  680.       continue;
  681.     }
  682.     if (dRec->rangeStart==iRec->position) {
  683. //take care of disposable common chars at START of block
  684.       do {
  685.         ulong dStart=dRec->rangeStart;
  686.         ulong iStart=iRec->rangeStart;
  687.         ulong n=0;
  688.         ulong n0=0;
  689. //take care of common white space:
  690.         while (oldText[n+dStart]==newText[n+iStart]) {
  691.           if (isAlpha(oldText[n+dStart])) break;
  692.           n++;
  693.         }
  694. //take care of common alpha but it must be a whole word:
  695.         n0=n;
  696.         while (oldText[n+dStart]==newText[n+iStart]) {
  697.           if (isAlpha(oldText[n+dStart])) {
  698.             n++;
  699.             if (0==isAlpha(oldText[n+dStart])) {//success
  700.               n0=n;
  701.               break;
  702.             }
  703.           }
  704.         }
  705.         if (n0) {
  706.           dRec->position+=dStart-dRec->rangeStart+n0;
  707.           dRec->rangeStart=dStart+n0;
  708.           iRec->position+=iStart-iRec->rangeStart+n0;
  709.           iRec->rangeStart=iStart+n0;
  710.         } else break;
  711.       } while (oldText[dRec->rangeStart]==
  712.           newText[iRec->rangeStart]);
  713.  
  714. //take care of disposable common chars at END of block
  715.       do {
  716.         ulong dEnd=dRec->rangeEnd;
  717.         ulong iEnd=iRec->rangeEnd;
  718.         ulong n=0;
  719.         ulong n0=0;
  720.  
  721. //take care of common alpha but it must be a whole word:
  722.         while (oldText[dEnd-n]==newText[iEnd-n]) {
  723.           if (isAlpha(oldText[dEnd-n])) {
  724.             n++;
  725.             if (0==isAlpha(oldText[dEnd-n])) {//success
  726.               n0=n;
  727.               break;
  728.             }
  729.           }
  730.         }
  731.         n=n0;
  732. //take care of common white space:
  733.         while (oldText[dEnd-n]==newText[iEnd-n]) {
  734.           if (isAlpha(oldText[dEnd-n])) break;
  735.           n++;
  736.         }
  737.         if (n) {
  738.           iRec->rangeEnd=iEnd-n;
  739.           dRec->rangeEnd=dEnd-n;
  740.         } else break;
  741.       } while (oldText[dRec->rangeEnd]==
  742.           newText[iRec->rangeEnd]);
  743.       if ((long)(dRec->rangeStart)>(long)(dRec->rangeEnd)) {
  744.         dRec->type=nullRec;
  745.         eliminated++;
  746.       }
  747.       if ((long)(iRec->rangeStart)>(long)(iRec->rangeEnd)) {
  748.         iRec->type=nullRec;
  749.         eliminated++;
  750.       }
  751.     } else while (iRec>diffs) { //find next lower iRec
  752.       iRec--;
  753.       if (insertedText==iRec->type) goto top_of_loop;
  754.     }
  755.     dRec--;
  756.   }
  757.   if (eliminated) ExtractNullRecs(diffs,numDiffRecs);
  758.  
  759.   return eliminated;
  760. }
  761.  
  762. /*The FindWordDifferences function is primarily a
  763.   collection of calls to the other routines.
  764.   In addition, it tries to eliminate parts of the texts
  765.   from processing which are completely identical at the
  766.   start or the tail ends of the texts.
  767.   If an insufficient number of DiffRecs was allocated,
  768.   and maxDiffRecs is reached while processing the texts,
  769.   the function returns this value without further ado.
  770. */
  771. short FindWordDifferences (
  772.   char  *oldText,     /* pointer to old version of text */
  773.   char  *newText,     /* pointer to new version of text */
  774.   ulong numOldChars,  /* number of characters in oldText */
  775.   ulong numNewChars, /* number of characters in newText */
  776.   DiffRec diffs[],   /* pointer to preallocated array
  777.                 where text differences are to be stored */
  778.   ulong maxDiffRecs  /* number of DiffRecs preallocated */
  779. )
  780. {
  781.   ulong           numSameHead,numSameTail;
  782.   long            numUniqueOldChars;
  783.   long            numUniqueNewChars;
  784.   short           numDiffRecs=0;
  785.   register char*  OTx=oldText;
  786.   register char*  NTx=newText;
  787.   register char*  OTlimit;
  788.   long            deltaChars=numOldChars-numNewChars;
  789.  
  790.   if (deltaChars>0) OTlimit=oldText+numNewChars;
  791.   else OTlimit=oldText+numOldChars;
  792.  
  793. //check for common head:
  794.   while (OTx<OTlimit) {
  795.     if (*OTx != *NTx) break;
  796.     OTx++;
  797.     NTx++;
  798.   }
  799.  
  800.   if ((isAlpha(*OTx)) || (isAlpha(*NTx))) {
  801. //backtrack to start of word
  802.     while ((OTx>oldText) && (isAlpha(OTx[-1]))) OTx--;
  803.     if (OTx>oldText) OTx--; //grab previous WSP
  804.   }
  805.  
  806.   numSameHead=OTx-oldText;
  807.  
  808. //check for common tail:
  809.   OTx=oldText+numOldChars-1;
  810.   NTx=newText+numNewChars-1;
  811.   if (deltaChars>0) OTlimit=oldText+deltaChars;
  812.   else OTlimit=oldText;
  813.   while (OTx>OTlimit) {
  814.     if (*OTx != *NTx) break;
  815.     OTx--;
  816.     NTx--;
  817.   }
  818.  
  819.   if ((isAlpha(*OTx)) || (isAlpha(*NTx))) {
  820. //track to end of word
  821.     while ((OTx<oldText+numOldChars-1)
  822.         && (isAlpha(OTx[1]))) OTx++;
  823.   }
  824.   numSameTail=oldText-OTx+numOldChars-1;
  825.  
  826.   numUniqueOldChars=numOldChars-numSameTail-numSameHead;
  827.   numUniqueNewChars=numNewChars-numSameTail-numSameHead;
  828.  
  829. /*These values may be negative!
  830.   If both are negative, old and new texts are identical,
  831.   and the function can return immediately.
  832. */
  833.   if ((numUniqueOldChars<0) && (numUniqueNewChars<0))
  834.         return 0;
  835.  
  836. #if countWords
  837.   GetSnippetStore(3+
  838.         WordCount(oldText+numSameHead,numUniqueOldChars));
  839. #else
  840.   GetSnippetStore(3+
  841.         numUniqueOldChars/averageWordSize);
  842. #endif
  843.   if (numUniqueOldChars>0)
  844.         ParseOldText(oldText,numSameHead,numUniqueOldChars);
  845.  
  846.   numDiffRecs+=
  847.         ParseNewText(oldText,newText,diffs,
  848.         numSameHead,numUniqueOldChars,numUniqueNewChars,
  849.         maxDiffRecs);
  850.  
  851.   numDiffRecs+=
  852.         CollectDeletes(&diffs[numDiffRecs],oldText,newText,
  853.         maxDiffRecs-numDiffRecs);
  854.  
  855.   numDiffRecs-=
  856.         ReduceInsDelPairs(diffs,numDiffRecs,oldText,newText);
  857.  
  858.   free(snippetStore);
  859.  
  860.   return numDiffRecs;
  861. }
  862.